import "babel-polyfill";
import {islice} from "../algorithm/array";

const block_size = 512;
const {floor} = Math;

export default class Deque {
    block = [];

    constructor() {
        this.begin = new DequeIterator(this);
        this.end = new DequeIterator(this);
        this.push(...arguments);
    }

    get [Symbol.toStringTag]() {
        return "Deque";
    }

    get length() {
        return this.begin.distance(this.end);
    }
    _get(index) {
        return this.block[index.block][index.index];
    }
    _set(index, value) {
        return this.block[index.block][index.index] = value;
    }
    get(index) {
        if (index >= 0 && index < this.length) {
            index += this.begin.index;
            return this.block[floor(index / block_size)][index % block_size];
        } else {
            return;
        }
    }
    set(index, value) {
        if (index >= 0 && index < this.length) {
            index += this.begin.index;
            this.block[floor(index / block_size)][index % block_size] = value;
        }
        return value;
    }

    *_iter() {
        for (let begin = new DequeIterator(this, this.begin); !begin.eq(this.end); begin.next()) {
            yield begin;
        }
    }
    *[Symbol.iterator]() {
        for (let iter of this._iter()) {
            yield this._get(iter);
        }
    }

    push() {
        const {block, end} = this;
        for (let x of arguments) {
            if (end.index === 0) {
                block.push(new Array(block_size));
            }
            this._set(end, x);
            end.next();
        }
        return this.length;
    }
    pop() {
        if (this.begin.eq(this.end)) {
            return;
        } else if (this.end.index === 1) {
            this.end.index = 0;
            return this.block.pop()[0];
        } else {
            return this._get(this.end.prev());
        }
    }
    shift() {
        if (this.begin.eq(this.end)) {
            return;
        } else if (this.begin.index === block_size - 1) {
            this.begin.index = 0;
            --this.end.block;
            return this.block.shift()[block_size - 1];
        } else {
            let x = this._get(this.begin);
            this.begin.next();
            return x;
        }
    }
    unshift() {
        const {block, begin, end} = this;
        for (var i = arguments.length; --i >= 0;) {
            if (begin.index === 0) {
                block.unshift(new Array(block_size));
                block[0][begin.index = block_size - 1] = arguments[i];
                ++end.block;
            } else {
                this._set(begin.prev(), arguments[i]);
            }
        }
        return this.length;
    }

    forEach(callback, thisArg) {
        var index = 0;
        for (let iter of this._iter()) {
            callback.call(thisArg, this._get(iter), index++, this);
        }
    }
    map(callback, thisArg) {
        var result = new Deque();
        result.block = this.block.slice();
        result.begin = new DequeIterator(result, this.begin);
        result.end = new DequeIterator(result, this.end);
        var index = 0;
        for (let iter of this._iter()) {
            result.set(iter, callback.call(thisArg, this._get(iter), index++, this));
        }
        return result;
    }
    filter(callback, thisArg) {
        var result = new Deque();
        var index = 0;
        for (let iter of this._iter()) {
            result.push(callback.call(thisArg, this._get(iter), index++, this));
        }
        return result;
    }

    slice(start = 0, stop = Infinity) {
        var length = this.length;
        if (start <= -length) {
            start = 0;
        } else if (start < 0) {
            start += this.length;
        } else if (start > length) {
            start = length;
        }
        if (stop <= -length) {
            stop = 0;
        } else if (stop < 0) {
            stop += this.length;
        } else if (stop > length) {
            stop = length;
        }

        var result = new Deque();
        if (start >= stop) {
            return result;
        }
        var begin = new DequeIterator(this, this.begin).go(start);
        var end = new DequeIterator(this, this.begin).go(stop);
        result.block = [...this.block::islice(
            begin.block,
            end.index === 0 ? end.block : end.block + 1
        )::map(x => x.slice())];
        result.begin = new DequeIterator(result, begin);
        result.end = new DequeIterator(result, {block: end.block - begin.block, index: end.index});
        return result;
    }

    *islice(start = 0, stop = Infinity) {
        var length = this.length;
        if (start <= -length) {
            start = 0;
        } else if (start < 0) {
            start += this.length;
        } else if (start > length) {
            start = length;
        }
        if (stop <= -length) {
            stop = 0;
        } else if (stop < 0) {
            stop += this.length;
        } else if (stop > length) {
            stop = length;
        }

        if (start >= stop) {
            return;
        }
        var begin = new DequeIterator(this, this.begin).go(start);
        var end = new DequeIterator(this, this.begin).go(stop);
        while (!begin.eq(end)) {
            yield this._get(begin);
            begin.next();
        }
    }
};

var DequeIterator = class {
    constructor(deque, iter = {block: 0, index: 0}) {
        this.deque = deque;
        this.block = iter.block;
        this.index = iter.index;
    }

    eq(other) {
        return this.deque === other.deque && this.block === other.block && this.index === other.index;
    }
    next() {
        if (this.index === block_size - 1) {
            ++this.block;
            this.index = 0;
        } else {
            ++this.index;
        }
        return this;
    }
    prev() {
        if (this.index === 0) {
            --this.block;
            this.index = block_size - 1;
        } else {
            --this.index;
        }
        return this;
    }
    go(distance) {
        this.index += distance;
        this.block += floor(this.index / block_size);
        this.index %= block_size;
        if (this.index < 0) {
            this.index += block_size;
        }
        return this;
    }
    distance(other) {
        return (other.block - this.block) * block_size + (other.index - this.index);
    }
};
